package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.ListNode;
import com.zjw.algorithm.utils.Utils;

import java.util.ArrayList;
import java.util.List;

public class _重排链表 {

    public static void main(String[] args) {
        ListNode head = Utils.asNodeList(new int[]{1, 2});
        new _重排链表().reorderList2(head);
        System.out.println(Utils.toString(head));
    }


    public void reorderList2(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode head2 = head.next;
        ListNode moveP = head2.next;
//        int count = 1;

        ListNode p1 = head;
        ListNode p2 = head2;
        //以下是奇偶划分
//        while (moveP != null) {
//            if ((count & 1) == 0) {
//                //偶数
//                p2.next = moveP;
//                p2 = p2.next;
//            } else {
//                p1.next = moveP;
//                p1 = p1.next;
//            }
//            ListNode next = moveP.next;
//            //先断开
//            moveP.next = null;
//            //计数
//            moveP = next;
//            count++;
//        }
        //以下是找链表中间点
        ListNode pFast = head;
        ListNode pSlow = head;
        ListNode pSlowPre = null;
        while (pFast != null && pFast.next != null) {
            pFast = pFast.next.next;
            pSlowPre = pSlow;
            pSlow = pSlow.next;
        }
        head2 = pSlow;
        //断开
        pSlowPre.next = null;

        head2 = re(head2);
        moveP = head;
        p2 = head2;
        ListNode movePref = null;
        while (moveP != null && p2 != null) {
            ListNode next = moveP.next;
            //p2插在 moveP he next之间，
            ListNode p2Next = p2.next;
            p2.next = null;
            moveP.next = p2;
            p2.next = next;

            //update
            movePref = p2;
            p2 = p2Next;
            moveP = next;
        }

        if (p2 != null){
            //more 1
            movePref.next = p2;
        }
    }

    //反转链表
    private ListNode re(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode p1 = head;
        ListNode p2 = head.next;

        p1.next = null;

        while (p2 != null) {
            ListNode next = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = next;
        }

        return p1;
    }

    public void reorderList(ListNode head) {
        List<ListNode> record = new ArrayList<>();

        if (head == null) {
            return;
        }

        ListNode p = head;
        while (p != null) {
            record.add(p);
            p = p.next;
        }

        int size = record.size();
        p = head;
        for (int i = 1; i <= size / 2; i++) {
            ListNode node1 = record.get(i);
            ListNode node2 = record.get(size - i);
            if (i != size - i) {
                p.next = node2;
                node2.next = node1;
                p = node1;
                p.next = null;
            } else {
                p.next = node1;
                node1.next = null;
                p = node1;
            }
        }
    }
}
